﻿#pragma once
#include<vector>
#include<iostream>
#include<map>
#include<queue>
#include"UnionFind.hpp"

using namespace std;


//矩阵图
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
private:
	struct EdgeNode
	{
		size_t _srci;
		size_t _dsti;
		W _w;

		EdgeNode(const W& w)
			:_srci(-1),
			_dsti(-1),
			_w(w)
		{}
	};
	typedef EdgeNode Edge;
	typedef Graph<V, W, MAX_W, Direction> self;

	struct GreaterEdge
	{
		bool operator()(const Edge& e1, const Edge& e2)
		{
			return e1._w > e2._w;
		}
	};
public:
	Graph() = default;
	Graph(const vector<V>& vertexs)
		:_vertexs(vertexs)
	{
		size_t num = vertexs.size();
		for (size_t i = 0; i < num; i++)
		{
			_IndexMap[vertexs[i]] = i;
		}

		_matrix.resize(num);
		for (auto& e : _matrix)
		{
			e.resize(num, MAX_W);
		}
	}

	size_t FindVertex(const V& vectex)
	{
		auto ret=_IndexMap.find(vectex);
		
		if (ret != _IndexMap.end())
		{
			return ret->second;
		}
		else
		{
			throw invalid_argument("No such vertex");
			return -1;
		}
	}

	bool AddEdge(const V& src, const V& dst, const W& w)
	{
		size_t srci = FindVertex(src);
		size_t dsti = FindVertex(dst);

		if (srci == -1 || dsti == -1)
			return false;

		return _AddEdge(srci, dsti, w);
	}

	void Print()
	{
		// 打印顶点和下标映射关系
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << _vertexs[i] << "-" << i << " ";
		}
		cout << endl << endl;
		cout << " ";
		for (size_t i = 0; i < _vertexs.size(); ++i)
		{
			cout << i << " ";
		}
		cout << endl;
		// 打印矩阵
		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			cout << i << " ";
			for (size_t j = 0; j < _matrix[i].size(); ++j)
			{
				if (_matrix[i][j] != MAX_W)
					cout << _matrix[i][j] << " ";
				else
					cout << "#" << " ";
			}
			cout << endl;
		}
		cout << endl << endl;
		// 打印所有的边
		for (size_t i = 0; i < _matrix.size(); ++i)
		{
			for (size_t j = 0; j < _matrix[i].size(); ++j)
			{
				if (i < j && _matrix[i][j] != MAX_W)
				{
					cout << _vertexs[i] << "-" << _vertexs[j] << ":" <<
						_matrix[i][j] << endl;
				}
			}
		}
	}

	//Kruskal算法生成最小生成树
	W Kruskal(self& MinTree)
	{
		size_t VertexNum = _vertexs.size();
		
		//初始化最小生成树
		MinTree._IndexMap = _IndexMap;
		MinTree._vertexs = _vertexs;
		MinTree._matrix.resize(VertexNum);
		for (auto& e:MinTree._matrix)
		{
			e.resize(VertexNum, MAX_W);
		}

		//返回值——权值的和
		W ret = W();

		//用并查集来记录是否有重复的结点
		UnionFind record(VertexNum);
		//用优先级队列来依次取出最小的边
		priority_queue<Edge,vector<Edge>,GreaterEdge> tmp;

		//插入所有的边
		for (size_t i = 0; i < VertexNum; i++)
		{
			for (size_t j = 0; j < VertexNum; j++)
			{
				if (_matrix[i][j] != MAX_W)
				{
					Edge ins(_matrix[i][j]);
					ins._srci = i;
					ins._dsti = j;
					tmp.push(ins);
				}
			}
		}

		//一共VertexNum-1条边
		size_t EdgeNum = VertexNum - 1;

		//当所有边被取完，或者已经取到了足够的边时才结束
		while (!tmp.empty() && EdgeNum != 0)
		{
			const Edge& min = tmp.top();

			//只有两个边不在同一个集合，才可以采用这条边
			if (record.Union(min._srci, min._dsti))
			{
				EdgeNum--;
				ret += min._w;
				MinTree._AddEdge(min._srci, min._dsti, min._w);
			}

			tmp.pop();
		}

		if (EdgeNum)
		{
			//如果EdgeNum不为0，表示取到的边不足，没有生成最小生成树
			return W();
		}
		else
		{
			return ret;
		}

	}

	//Prim算法生成最小生成树
	W Prim(self& MinTree, const V& src)
	{
		size_t VertexNum = _vertexs.size();

		//初始化最小生成树
		MinTree._IndexMap = _IndexMap;
		MinTree._vertexs = _vertexs;
		MinTree._matrix.resize(VertexNum);
		for (auto& e : MinTree._matrix)
		{
			e.resize(VertexNum, MAX_W);
		}

		W ret = W();

		//用vector来记录每个结点是否被取到
		vector<bool> record(VertexNum, false);
		size_t EdgeNum = VertexNum - 1;
		
		//从src对应的结点开始找边
		size_t cur = MinTree.FindVertex(src);
		//用优先级队列实现
		priority_queue<Edge, vector<Edge>, GreaterEdge> tmp;

		do
		{
			//如果这个结点还没有被记录过，则判断该结点相连的所有边
			if (record[cur] == false)
			{
				record[cur] = true;
				for (size_t i = 0; i < VertexNum; i++)
				{
					//当dst没有被记录，表示这个边有可能被取到，插入队列中
					if (record[i] == false && _matrix[cur][i] != MAX_W)
					{
						Edge ins(_matrix[cur][i]);
						ins._srci = cur;
						ins._dsti = i;

						tmp.push(ins);
					}
				}
			}

			Edge MinEdge = tmp.top();
			//如果没有被记录，则进入最小生成树
			if (record[MinEdge._dsti] == false)
			{
				MinTree._AddEdge(MinEdge._srci, MinEdge._dsti, MinEdge._w);
				cur = MinEdge._dsti;
				EdgeNum--;
				ret += MinEdge._w;
			}

			tmp.pop();
		} while (!tmp.empty()&&EdgeNum!=0);

		if (EdgeNum)
		{
			return W();
		}
		else
		{
			return ret;
		}
	}

	//Dijkstra算法找最小路径
	void Dijkstra(const V& src, vector<W>& dst_w, vector<int>& ParentPath)
	{
		size_t VertexNum = _vertexs.size();
		size_t srci = FindVertex(src);

		//初始化dst_w和ParentPath
		dst_w.resize(VertexNum, MAX_W);
		dst_w[srci] = W();
		ParentPath.resize(VertexNum, -1);
		ParentPath[srci] = srci;

		size_t cur = srci;
		//需要循环VertexNum-1次，来找到到达所有边的最短路径
		for (size_t i = 0; i < VertexNum - 1; i++)
		{
			for (size_t j = 0; j < VertexNum; j++)
			{
				//如果权值存在并且目的地结点没有被记录过
				if (_matrix[cur][j] != MAX_W && ParentPath[j] == -1)
				{
					//如果更新后的数据更小，则改变
					//否则不变
					dst_w[j] = min(dst_w[j], dst_w[cur] + _matrix[cur][j]);
				}
			}

			//遍历dst_W寻找最小路径
			W Minw = MAX_W;
			size_t Minp = -1;
			for (size_t j = 0; j < VertexNum; j++)
			{
				if (ParentPath[j] == -1 && dst_w[j] < Minw)
				{
					Minw = dst_w[j];
					Minp = j;
				}
			}

			dst_w[Minp] = Minw;
			ParentPath[Minp] = cur;
			cur = Minp;
		}
	}

	bool Bellman_Ford(const V& src, const vector<W>& dst_w, const vector<int>& ParentPath)
	{
		size_t VertexNum = _vertexs.size();
		size_t srci = FindVertex(src);

		//初始化dst_w和ParentPath
		dst_w.resize(VertexNum, MAX_W);
		dst_w[srci] = W();
		ParentPath.resize(VertexNum, -1);
		ParentPath[srci] = srci;

		//循环O(N^3)
		for (size_t i = 0; i < VertexNum; i++)
		{
			bool exchange = false;
			//j是遍历每个顶点，以当前顶点为出发点src
			for (size_t j = 0; j < VertexNum; j++)
			{
				//k相当于目的点dst
				for (size_t k = 0; k < VertexNum; k++)
				{
					//当权值存在时，尝试是否可以被更新
					if (_matrix[j][k] != MAX_W && dst_w[k] > dst_w[j] + _matrix[j][k])
					{
						dst_w[k] = dst_w[j] + _matrix[j][k];
						ParentPath[k] = j;
						exchange = true;
					}
				}
			}

			//如果某次循环没有被更新，则接下来的循环也肯定不会再次被更新
			if (exchange == false)
			{
				break;
			}
		}

		for (size_t i = 0; i < VertexNum; i++)
		{
			for (size_t j = 0; j < VertexNum; j++)
			{
				//检查负权回路
				//有负权回路，不可能找到最短路径
				if (_matrix[i][j] != MAX_W && _matrix[i][j] + dst_w[i] < dst_w[j])
				{
					//因为如果有负权回路，则一定会不断更新到最小不会终止
					//而如果没有负权回路，更新VertexNum次一定会更新完，如果还可以更新则说明存在负权回路
					//负权回路是没有最短路径的，一直转圈可以不断减少路径
					return false;
				}
			}
		}

		return true;
	}

	void Floyd_Warshall(vector<vector<W>>& dst_w, vector<vector<int>>& ParentPath)
	{
		size_t VertexNum = _vertexs.size();

		//初始化
		dst_w.resize(VertexNum);
		ParentPath.resize(VertexNum);
		for (size_t i = 0; i < VertexNum; i++)
		{
			dst_w[i].resize(VertexNum, MAX_W);
			ParentPath[i].resize(VertexNum, -1);
		}

		//直接相连的路径初始化
		//dst_w存的是从i到j的最小值
		//ParentPath存的是从i到j的最小路径中j的前一个结点
		for (size_t i = 0; i < VertexNum; i++)
		{
			for (size_t j = 0; j < VertexNum; j++)
			{
				if (_matrix[i][j] != MAX_W)
				{
					dst_w[i][j] = _matrix[i][j];
					ParentPath[i][j] = i;
				}
				
				if (i == j)
				{
					dst_w[i][j] = W();
					ParentPath[i][j] = -1;
				}
			}
		}

		//以顶点k为中间结点，依次寻找最小路径
		for (size_t k = 0; k < VertexNum; k++)
		{
			//以K为中间结点，则路径中只会包含遍历过的k
			//比方说，当k=0，则只会有x->0->y，不会有x->...->0->y，因为如果存在这种情况，则表示dst_w中存了x->...->0
			//但是如果存了x->...->0，则是以其他为中间节点，和目前只以0为过中间节点相违背
			for (size_t i = 0; i < VertexNum; i++)
			{
				for (size_t j = 0; j < VertexNum; j++)
				{
					if ((dst_w[i][k] != MAX_W && dst_w[k][j] != MAX_W) && (dst_w[i][k] + dst_w[k][j] < dst_w[i][j]))
					{
						dst_w[i][j] = dst_w[i][k] + dst_w[k][j];
						ParentPath[i][j] = ParentPath[k][j];
					}
				}
			}
		}
	}

	// 打印最短路径的逻辑算法
	void PrinrtShotPath(const V& src, const vector<W>& dist, const vector<int>& ParentPath)
	{
		size_t N = _vertexs.size();
		size_t srci = FindVertex(src);
		for (size_t i = 0; i < N; ++i)
		{
			if (i == srci)
				continue;

			vector<int> path;
			int parenti = i;
			while (parenti != srci)
			{
				path.push_back(parenti);
				parenti = ParentPath[parenti];
			}
			path.push_back(srci);
			reverse(path.begin(), path.end());
			for (auto pos : path)
			{
				cout << _vertexs[pos] << "->";
			}
			cout << dist[i] << endl;
		}
	}
private:
	map<V, size_t> _IndexMap;
	vector<V> _vertexs;
	vector<vector<W>> _matrix;
	
	bool _AddEdge(size_t srci, size_t dsti, const W& w)
	{
		if (_matrix[srci][dsti] != MAX_W)
			return false;

		_matrix[srci][dsti] = w;
		if (Direction == false)
			_matrix[dsti][srci] = w;

		return true;
	}
};


//邻接表
template<class V,class W,bool Direction=false>
class LinkEdgeGraph
{
private:
	struct EdgeNode
	{
		size_t _srci;
		size_t _dsti;
		W _w;
		EdgeNode* _next;

		EdgeNode(const W& w)
			:_srci(-1),
			_dsti(-1),
			_w(w),
			_next(nullptr)
		{}
	};
public:
	typedef EdgeNode Edge;

	LinkEdgeGraph() = default;

	LinkEdgeGraph(const vector<V>& vertexs)
		:_vertexs(vertexs)
	{
		for (size_t i = 0; i < vertexs.size(); i++)
		{
			_IndexMap[vertexs[i]] = i;
		}

		_linkTable.resize(vertexs.size(), nullptr);
	}

	size_t FindVertex(const V& vertex)
	{
		auto ret = _IndexMap.find(vertex);
		if (ret != _IndexMap.end())
			return ret->second;

		return -1;
	}

	bool AddEdge(const V& src,const V& dst,const W& w)
	{
		size_t srci = FindVertex(src);
		size_t dsti = FindVertex(dst);

		if (srci == -1 || dsti == -1)
			return false;

		return _AddEdge(srci, dsti, w);
	}
private:
	map<V, size_t> _IndexMap;
	vector<V> _vertexs;
	vector<Edge*> _linkTable;

	bool _AddEdge(size_t srci, size_t dsti, const W& w)
	{
		Edge* cur = _linkTable[srci];
		while (cur)
		{
			if (cur->_dsti == dsti)
				return false;
			cur = cur->_next;
		}

		//采用头插的方式实现
		Edge* ins = new Edge(w);
		ins->_srci = srci;
		ins->_dsti = dsti;
		ins->_next = _linkTable[srci];
		_linkTable[srci] = ins;

		if (Direction == false)
		{
			swap(srci, dsti);
			Edge* ins = new Edge(w);
			ins->_srci = srci;
			ins->_dsti = dsti;
			ins->_next = _linkTable[srci];
			_linkTable[srci] = ins;
		}

		return true;
	}
};